#!/usr/bin/python
# call the file with ./greedyEval.py <directory> <0 - Kyle, 1 - Lauren, 2 - Catie> <gr - Greedy, sa - Simulated Annealing>

import glob
import Image
import math
import os
import sys
import Queue
import random
import time
import string
from xml.dom.minidom import parseString

# This provides the conversion between text length to pixel dimension of a QR code
# This was pulled from the table located at: http://www.google.com/url?q=http%3A%2F%2Fwww.qrstuff.com%2Fblog%2F2011%2F11%2F23%2Fqr-code-minimum-size&sa=D&sntz=1&usg=AFQjCNF8QQ4EAdHJdeFmQP-cX_C2pJWPZA
# We added 10 pixels as a "buffer" to remove bug where a QR code is along an axis
texttopixels = [
	("26", 100),
	("49", 110),
	("72", 120),
	("98", 130),
	("125", 150),
	("163", 160),
	("203", 170),
	("249", 180),
	("298", 190),
	("351", 200),
	("407", 210),
	("468", 220),
	("534", 240),
	("601", 250),
	("669", 260),
	("739", 280)
]

# This provides the number of pixels a QR code will move (in x and y)
directions ={
        "N" : (0,-10),
        "NE": (10,-10),
        "E" : (10,0),
        "SE": (10,10),
        "S" : (0,10),
        "SW": (-10,10),
        "W" : (-10,0),
        "NW": (-10,-10),
        "Stop": (0,0)
        }

# These are the XML tags used to parse the file
NUM_LABELS_LABEL = 'NumLabels'
ALIGNMENT_LABEL = 'Alignment'
ORIGINAL_X1_LABEL = 'x1original'
ORIGINAL_Y1_LABEL = 'y1original'
X1_LABEL = 'x1'
X2_LABEL = 'x2'
Y1_LABEL = 'y1'
Y2_LABEL = 'y2'
TEXT_LABEL = 'text'
QR_SIZE_LABEL = 'qrsize'
IMAGE_OVERLAP_LABEL = 'imageOverlap'
IMAGE_OVERLAP_WEIGHT = 'weightedOverlap'
LABEL_OVERLAP_LIST = 'labelOverlapList'
LABEL_OVERLAP_LABEL = 'labelOverlapValue'
SCALE_X_LABEL = 'ScaleX'
SCALE_Y_LABEL = 'ScaleY'

# These are Lauren's variables for the eval function, do not use otherwise!
WEIGHT_OVERLAPPED_LABEL = 1
WEIGHT_OVERLAPPED_IMAGE = 2
WEIGHT_X_DISTANCE_FROM_ORIGINAL = 1
WEIGHT_Y_DISTANCE_FROM_ORIGINAL = 1
MOVEMENT_THRESHOLD = 50


# The user needs to specify a folder which should contain:
# 1. Resized Image from Photoshop <name>.Resized.bmp
# 2. XML file <name>.SelMBs.xml
# 3. TXT file which contains the text we are using <name>.SelLabelsNoBoxes.txt
# 4. TXT file which contains the coefficients to the parameters (SOMEONE specify this)

# We should also supply arguments for each of the coefficients

labelInfo = [] # Global variable since we will need to access this across many methods
labels = [] #labels in form (evalFuncion, labelIndex, numTimesMoved)
imgWidth = 0 # Global variable to store width of an image
imgHeight = 0 # Global variable to store height of an image

def main():
	global imgWidth
	global imgHeight
        if len(sys.argv) < 4:
                print "please specify the path to the folder of data, can be a relative path and which evaluation function to use"
                sys.exit(-1)
        if not (sys.argv[2]=="0" or sys.argv[2]=="1" or sys.argv[2]=="2"):
                print "not an evaluation function option. please enter 0, 1, or 2"
                sys.exit(-1)
	if not (sys.argv[3] == "gr" or sys.argv[3] == "sa"):
		print "Please specify gr for greedy and sa for simulated annealing"
		sys.exit(-1)

        # parse folder from user supplied argument and fill in file lists
        os.chdir(sys.argv[1]) # input file location
        xmlList = glob.glob("*.SelMBs.xml")
	xmlList.sort()
        txtList = glob.glob("*.SelLabelsNoBoxes.txt")
	txtList.sort()
        bmpList = glob.glob("*.bmp")
	bmpList.sort()
        evalFunc = sys.argv[2]
        for i in range (len(bmpList)):
		# parse the XML file and store data about each label
            	del labelInfo[:] # clear the list first
            	del labels[:]
		createDictionary(xmlList[i], txtList[i], bmpList[i])
          	# update the coordinates since we are working with QR codes and not text labels
            	image = Image.open(bmpList[i])
                imgWidth = image.size[0]
                imgHeight = image.size[1]
		updateCoordinates()
		for label in labelInfo:
                        label[IMAGE_OVERLAP_LABEL] = getOverlap(label[X1_LABEL],label[Y1_LABEL],label[X2_LABEL],label[Y2_LABEL],bmpList[i])
                        label[IMAGE_OVERLAP_WEIGHT] = weightOverlap(label[X1_LABEL],label[Y1_LABEL],label[X2_LABEL],label[Y2_LABEL],bmpList[i])
                        label[LABEL_OVERLAP_LABEL] = getLabelOverlap(label,label[X1_LABEL],label[Y1_LABEL])
                        label[LABEL_OVERLAP_LIST] = labelOverlapList(label)
            	createPriorityQueue(evalFunc,bmpList[i])
		outputImage(bmpList[i],evalFunc, True)		
		# calling eval functions, start timing!
		#print labelInfo
		start = time.time()
		if (sys.argv[3] == "gr"):
			greedyAlgorithm(bmpList[i],evalFunc)
		elif (sys.argv[3] == "sa"):
                	simulatedAnnealing(bmpList[i],evalFunc)
		outputImage(bmpList[i],evalFunc, False)
		print "Run time",time.time()-start

# Input: dom from xml file
# Output: number of labels in the figure
def getNumLabels(dom):
	xmlTag = dom.getElementsByTagName(NUM_LABELS_LABEL)[0].toxml()
	return int(xmlTag.replace('<'+NUM_LABELS_LABEL+'>', '').replace('</'+NUM_LABELS_LABEL+'>', ''))

# Input: idx of label and the location contents
# Places the rest of the information in the dictionary
def extractLocation(idx, dom):
	labelContents = [X1_LABEL, Y1_LABEL, X2_LABEL, Y2_LABEL, ALIGNMENT_LABEL]
	for content in labelContents:
		xmlTag = dom.getElementsByTagName(content)[idx].toxml()
		labelInfo[idx][content] = int(xmlTag.replace('<'+content+'>', '').replace('</'+content+'>', ''))	

# Input: XML File and TXT file containing info about each label
# This will insert data into the labelInfo array
def createDictionary(xmlFile, txtFile, bmpFile):
	# Open the file, extract the data, close the file
	xmlf = open(xmlFile, 'r')
	data = xmlf.read()
	xmlf.close()
	dom = parseString(data)

	# Open the text file to extract one label at a time
	txtf = open(txtFile, 'r')

	for idx in range(getNumLabels(dom)):
		labelInfo.append({})
		line = txtf.readline()

		labelInfo[idx][TEXT_LABEL] = line
		labelInfo[idx][QR_SIZE_LABEL] = getNumPixels(len(line))
		xmlLabel = dom.getElementsByTagName('Label')[idx].toxml()
		extractLocation(idx, dom)
		
		xmlTag = dom.getElementsByTagName(SCALE_X_LABEL)[0].toxml()
                scaleX = float(xmlTag.replace('<'+SCALE_X_LABEL+'>', '').replace('</'+SCALE_X_LABEL+'>', ''))
		xmlTag = dom.getElementsByTagName(SCALE_Y_LABEL)[0].toxml()
                scaleY = float(xmlTag.replace('<'+SCALE_Y_LABEL+'>', '').replace('</'+SCALE_Y_LABEL+'>', ''))

		labelInfo[idx][X1_LABEL] = int(labelInfo[idx][X1_LABEL] * scaleX)
		labelInfo[idx][X2_LABEL] = int(labelInfo[idx][X2_LABEL] * scaleX)
		labelInfo[idx][Y1_LABEL] = int(labelInfo[idx][Y1_LABEL] * scaleY)
		labelInfo[idx][Y2_LABEL] = int(labelInfo[idx][Y2_LABEL] * scaleY)

# Input: # characters
# Output: # pixels
def getNumPixels(numChars):
	for key in texttopixels:
		if numChars < int(key[0]):
			return key[1]
	return -1

# Updating coordinates from original text label to QR code
# Left alignment - keep x1,y1, change x2 = x1 + QRpixel, y2 = y1 + QRpixel
# Center alignment - keep y1, change x1 = x1 + floor[(x2-x1-QRpixel)/2], x2 = x1 + QRpixel, y2 = y1 + QRpixel
# Right alignment - keep y1, x2, change x1 = x2 - QRpixel, y2 = y1 + QRpixel
def updateCoordinates():
        
	for label in labelInfo:
		alignment = label[ALIGNMENT_LABEL]
		if alignment == -1:
			label[X2_LABEL] = label[X1_LABEL] + label[QR_SIZE_LABEL]
		elif alignment == 0:
			label[X1_LABEL] += int(math.floor((label[X2_LABEL] - label[X1_LABEL] - label[QR_SIZE_LABEL])/2))
			label[X2_LABEL] = label[X1_LABEL] + label[QR_SIZE_LABEL]
		elif alignment == 1:
			label[X1_LABEL] = label[X2_LABEL] - label[QR_SIZE_LABEL]
		else:
			print "bad label!"
			sys.exit(-1)
		# regardless, y2 will equal y1 + qr size
		label[Y2_LABEL] = label[Y1_LABEL] + label[QR_SIZE_LABEL]
		
		# in order to begin evaluating, the QR codes must be inside the image
		if (label[X1_LABEL] < 0):
			label[X1_LABEL] = 0
			label[X2_LABEL] = label[X1_LABEL] + label[QR_SIZE_LABEL]
		elif (label[X2_LABEL] >= imgWidth):
			label[X2_LABEL] = imgWidth-1 # -1 because it is an array index
			label[X1_LABEL] = label[X2_LABEL] - label[QR_SIZE_LABEL]
		if (label[Y2_LABEL] >= imgHeight):
			label[Y2_LABEL] = imgHeight-1 # -1 because it is an array index
			label[Y1_LABEL] = label[Y2_LABEL] - label[QR_SIZE_LABEL]

		# kept for the movement from original calculation
		label[ORIGINAL_X1_LABEL] = label[X1_LABEL]
		label[ORIGINAL_Y1_LABEL] = label[Y1_LABEL]

"""
creates priority queue with labels in the form:(-evalFuncion, labelIndex, numTimesMoved)
evalFunction is negative because priority queues have lowest value on top
"""
def createPriorityQueue(evalFunc, img):
        for i,label in enumerate(labelInfo):
            labels.append([evaluationFunction(evalFunc,label, label[X1_LABEL], label[Y1_LABEL], True, img),i,0])
        
"""
returns number of pixels of other labels that are overlapped by current label in new position.
Will double count for pixels if label overlaps two other labels at the same location

"""
def getLabelOverlap(currentLabel, newX1, newY1):
        overlap = 0
        for label in labelInfo:
                if currentLabel != label:
                        currentLabelXRange = set(range(newX1, newX1+currentLabel[QR_SIZE_LABEL]))
                        labelXRange = set(range(label[X1_LABEL], label[X2_LABEL]))
                        xIntersection = len(currentLabelXRange.intersection(labelXRange))
                        currentLabelYRange = set(range(newY1, newY1+currentLabel[QR_SIZE_LABEL]))
                        labelYRange = set(range(label[Y1_LABEL], label[Y2_LABEL]))
                        yIntersection = len(currentLabelYRange.intersection(labelYRange))
                        overlap += xIntersection*yIntersection                        
        return overlap


"""
returns evaluation function (linear function).  Distance is currently evaluated in both x and y directions.
(Lauren) Hasn't installed image module yet so that part is commented out.

"""
def evaluationFunction(evalFunc,label, newX1, newY1, labelMoved, img):
        if evalFunc == "0":
                return evalFuncKyle(label, newX1, newY1, labelMoved, img)
        elif evalFunc == "1":
                return evalFuncLauren(label, newX1, newY1, labelMoved, img)
        elif evalFunc == "2":
                return evalFuncCatie(label, newX1, newY1, labelMoved, img)

def evalFuncCatie(label, newX1, newY1, labelMoved, img):
        numOverlapWeight = 2.0
        labelOverlapWeight = 1.0
        imageOverlapWeight = 2.0
        weightOverlapWeight = 4.0
        distFromOrigWeight = .5
        
        
        score = 0
        score = distFromOrigWeight*distFromOriginalPlacement(label[ORIGINAL_X1_LABEL],label[ORIGINAL_Y1_LABEL],newX1,newY1)
        if labelMoved:
                overlap = getOverlap(newX1, newY1,newX1+label[QR_SIZE_LABEL], newY1+label[QR_SIZE_LABEL],img)
                score += imageOverlapWeight*overlap
                if not overlap == 0:
                        score += weightOverlapWeight*weightOverlap(newX1, newY1,newX1+label[QR_SIZE_LABEL], newY1+label[QR_SIZE_LABEL],img)
                score += numOverlapWeight*len(labelOverlapList(label))
                score += labelOverlapWeight*getLabelOverlap(label,newX1,newY1)
                
        else:
                score += numOverlapWeight*numOverlapWeight*len(label[LABEL_OVERLAP_LIST])
                score += labelOverlapWeight*label[LABEL_OVERLAP_LABEL]
                score += imageOverlapWeight*label[IMAGE_OVERLAP_LABEL]
                if not label[IMAGE_OVERLAP_LABEL]==0:
                        score += weightOverlapWeight*label[IMAGE_OVERLAP_WEIGHT]
        return score
        

def evalFuncLauren(label, newX1, newY1, labelMoved, img):
        if label[ALIGNMENT_LABEL]==-1:
                #left aligned
                WEIGHT_X_DISTANCE_FROM_ORIGINAL=3
                WEIGHT_Y_DISTANCE_FROM_ORIGINAL=1
        if label[ALIGNMENT_LABEL]==0:
                #center aligned
                WEIGHT_X_DISTANCE_FROM_ORIGINAL=2
                WEIGHT_Y_DISTANCE_FROM_ORIGINAL=2
        if label[ALIGNMENT_LABEL]==1:
                #right aligned
                WEIGHT_X_DISTANCE_FROM_ORIGINAL=3
                WEIGHT_Y_DISTANCE_FROM_ORIGINAL=1
        xDistanceFunc = WEIGHT_X_DISTANCE_FROM_ORIGINAL*math.fabs(newX1-label[ORIGINAL_X1_LABEL])
        yDistanceFunc = WEIGHT_Y_DISTANCE_FROM_ORIGINAL*math.fabs(newY1-label[ORIGINAL_Y1_LABEL])
        if not labelMoved:
                imageOverlap = WEIGHT_OVERLAPPED_IMAGE * label[IMAGE_OVERLAP_LABEL]
        else:
                imageOverlap = WEIGHT_OVERLAPPED_IMAGE * getOverlap(newX1, newY1,newX1+label[QR_SIZE_LABEL], newY1+label[QR_SIZE_LABEL],img)
        labelOverlap = WEIGHT_OVERLAPPED_LABEL * getLabelOverlap(label, newX1, newY1)
        function = imageOverlap + labelOverlap + xDistanceFunc + yDistanceFunc
                    #print imageOverlap, labelOverlap, xDistanceFunc, yDistanceFunc
        return function


def evalFuncKyle(label, newX1, newY1, labelMoved, img):
        # Set up coordinates based on whether the label has moved
	X1 = newX1 if labelMoved else label[X1_LABEL]
	Y1 = newY1 if labelMoved else label[Y1_LABEL]
	X2 = X1 + label[QR_SIZE_LABEL]
	Y2 = Y1 + label[QR_SIZE_LABEL]

	# Factors: distance from original position, QR code overlap, image overlap
	score = 0
	# Would like to reduce QR code overlap as much as possible, since it would ruin at least two labels
	# However, this should decrease in importance when there are fewer labels (base case: 1 label, 0 factor)
	score += (len(labelInfo)-1)*getLabelOverlap(label, newX1, newY1)
	# Would like to reduce QR code/image overlap second because it would ruin one label
	score += 5*getOverlap(X1, Y1, X2, Y2, img)
	# Would like to reduce displacement of QR code from original "text" position so the label is still representative
	score += 1*distFromOriginalPlacement(label[ORIGINAL_X1_LABEL], label[ORIGINAL_Y1_LABEL], X1, Y1)        
 
	return score

"""
algorithm picks worst placed item in queue, tries moving it in each of 8 directions and picks the one with the bestevaluation function.  If the label is moved over a threshold number of times, remove from queue
if total evaluation function drops below 0, algorithm will stop
"""
def greedyAlgorithm(img,evalFunc):
        print "starting greedy evaluation"
        while len(labels)!=0:
                directionsToTry = ["N", "E", "S", "W", "NE","NW","SE","SW"]
                random.shuffle(directionsToTry)
            
                #pick worst label
                label = max(labels)
                # if the score is <= 0, there no local improvements can be made
		if label[0] <= 0:
                    break
                # store the index of the labelInfo dictionary
		index = label[1]
                #want to find best movement (ie with smallest evaluationFunction, initially set to no movement)
                #TODO: if minEval == label[0] remove this line
		minEval = evaluationFunction(evalFunc,labelInfo[index], labelInfo[index][X1_LABEL], labelInfo[index][Y1_LABEL], False, img)
                minDirect = "Stop"
            
                while directionsToTry:
                    	#try moving five pixels in each of 8 directions
                    	newDirection = directionsToTry.pop()
                    	newX1 = labelInfo[index][X1_LABEL] + directions[newDirection][0]
			newX2 = newX1 + labelInfo[index][QR_SIZE_LABEL]
                    	newY1 = labelInfo[index][Y1_LABEL] + directions[newDirection][1]
			newY2 = newY1 + labelInfo[index][QR_SIZE_LABEL]
                    	if newX1 >= 0 and newY1 >= 0 and newX2 < imgWidth and newY2 < imgHeight:
                        	#evaluate
                        	newEval = evaluationFunction(evalFunc, labelInfo[index], newX1, newY1, True, img)
                        	if newEval <= minEval:
                            		minEval = newEval
                            		minDirect = newDirection
                            		
                #print minEval, minDirect
                labelInfo[index][X1_LABEL] += directions[minDirect][0]
                labelInfo[index][X2_LABEL] += directions[minDirect][0]
                labelInfo[index][Y1_LABEL] += directions[minDirect][1]
                labelInfo[index][Y2_LABEL] += directions[minDirect][1]
                
		# Update the score and number of times moved in the priority queue
		label[0] = minEval
                label[2] += 1
                
                
                
                #if not moved, put at end of priority queue by making negative
                #if moved, update evaluation functions and recalculate scores of all labels
                if directions[minDirect] == (0,0):
                    	label[0] = -label[0]
                else:
                        #Since moved, update stored calculations
                        labelInfo[index][IMAGE_OVERLAP_LABEL]= getOverlap(labelInfo[index][X1_LABEL],labelInfo[index][Y1_LABEL],
				labelInfo[index][X2_LABEL],labelInfo[index][Y2_LABEL], img)
                        labelInfo[index][IMAGE_OVERLAP_WEIGHT] = weightOverlap(labelInfo[index][X1_LABEL],labelInfo[index][Y1_LABEL],
				labelInfo[index][X2_LABEL],labelInfo[index][Y2_LABEL], img)
                        overlapList = list(labelInfo[index][LABEL_OVERLAP_LIST])
                        for i in range(len(overlapList)):
                                labelInfo[overlapList[i]][LABEL_OVERLAP_LIST] = labelOverlapList(labelInfo[overlapList[i]])
                                labelInfo[overlapList[i]][LABEL_OVERLAP_LABEL] = getLabelOverlap(labelInfo[overlapList[i]],labelInfo[overlapList[i]][X1_LABEL],labelInfo[overlapList[i]][Y1_LABEL])
                        labelInfo[index][LABEL_OVERLAP_LIST] = labelOverlapList(labelInfo[index])
                        #copied wrong -> should be not index[...]
                        for j in range(len(labelInfo[index][LABEL_OVERLAP_LIST])):
                                if j not in overlapList:
                                        labelInfo[labelInfo[index][LABEL_OVERLAP_LIST][j]][LABEL_OVERLAP_LIST] = labelOverlapList(labelInfo[labelInfo[index][LABEL_OVERLAP_LIST][j]])
                                        labelInfo[labelInfo[index][LABEL_OVERLAP_LIST][j]][LABEL_OVERLAP_LABEL] = getLabelOverlap(labelInfo[labelInfo[index][LABEL_OVERLAP_LIST][j]],labelInfo[labelInfo[index][LABEL_OVERLAP_LIST][j]][X1_LABEL],labelInfo[labelInfo[index][LABEL_OVERLAP_LIST][j]][Y1_LABEL])
                        #update priority queue
                    	for l in labels:
                        	labelIndex = l[1] # index of labelInfo
                        	l[0] = evaluationFunction(evalFunc, labelInfo[labelIndex],
					labelInfo[labelIndex][X1_LABEL], labelInfo[labelIndex][Y1_LABEL], False, img)
                        
                    
                #if image is moved over a threshold number of times, remove from queue
                if label[2] >= MOVEMENT_THRESHOLD:
                    	labels.remove(label)
        #print labelInfo
        

def simulatedAnnealing(img,evalFunc):
        print "starting simulated annealing"
        run = 0 # number of potential label changes within a stage
        madeChange = False # we want to stop if we converged for a stage
        stage = 0 # number of temperature changes
        temp = .5 # subject to change
        minEval = float('inf')
        while stage<=51:
                directionsToTry = ["N", "E", "S", "W"]
                score = 0
                for label in labelInfo:
                        score += evaluationFunction(evalFunc,label, label[X1_LABEL], label[Y1_LABEL], False, img)
                index = random.choice(labelInfo)
                inbounds = False
                while not inbounds:
                        newDirection = random.choice(directionsToTry)
                        newX1 = index[X1_LABEL] + directions[newDirection][0]
                        newY1 = index[Y1_LABEL] + directions[newDirection][1]
                        newX2 = index[X2_LABEL] + directions[newDirection][0]
                        newY2 = index[Y2_LABEL] + directions[newDirection][1]
                        #print newX1, newY1, newX2, newY2,imgWidth,imgHeight
                        if newX1 >= 0 and newY1 >= 0 and newX2 < imgWidth and newY2 < imgHeight:
                                inbounds = True
                newScore = 0
                for label in labelInfo:
                        if label == index:
                                newScore += evaluationFunction(evalFunc,label, newX1, newY1, True, img)
                        else:
                                newScore += evaluationFunction(evalFunc,label, label[X1_LABEL], label[Y1_LABEL], False, img)
                #update image and label overlap if necessary
                prob = temp/(1+abs(newScore-score)) # probability that we accept a bad change
                if newScore <= score or flipCoin(prob):
                        index[X1_LABEL] += directions[newDirection][0]
                        index[X2_LABEL] += directions[newDirection][0]
                        index[Y1_LABEL] += directions[newDirection][1]
                        index[Y2_LABEL] += directions[newDirection][1]
                        index[IMAGE_OVERLAP_LABEL] = getOverlap(index[X1_LABEL],index[Y1_LABEL],index[X2_LABEL],index[Y2_LABEL],img)   
                        madeChange = True
                        index[IMAGE_OVERLAP_WEIGHT] = weightOverlap(index[X1_LABEL],index[Y1_LABEL],
				index[X2_LABEL],index[Y2_LABEL], img)
                        overlapList = list(index[LABEL_OVERLAP_LIST])
                        for i in range(len(overlapList)):
                                labelInfo[overlapList[i]][LABEL_OVERLAP_LIST] = labelOverlapList(labelInfo[overlapList[i]])
                                labelInfo[overlapList[i]][LABEL_OVERLAP_LABEL] = getLabelOverlap(labelInfo[overlapList[i]],labelInfo[overlapList[i]][X1_LABEL],labelInfo[overlapList[i]][Y1_LABEL])
                        index[LABEL_OVERLAP_LIST] = labelOverlapList(index)
                        for j in range(len(index[LABEL_OVERLAP_LIST])):
                                if j not in overlapList:
                                        labelInfo[index[LABEL_OVERLAP_LIST][j]][LABEL_OVERLAP_LIST] = labelOverlapList(labelInfo[index[LABEL_OVERLAP_LIST][j]])
                                        labelInfo[index[LABEL_OVERLAP_LIST][j]][LABEL_OVERLAP_LABEL] = getLabelOverlap(labelInfo[index[LABEL_OVERLAP_LIST][j]],labelInfo[index[LABEL_OVERLAP_LIST][j]][X1_LABEL],labelInfo[index[LABEL_OVERLAP_LIST][j]][Y1_LABEL])
                        #print "Made Change"
                        minEval = min(newScore, minEval)
                run += 1
                if run == 200:
                        if madeChange == False and score == minEval:
                                break
                        else: # if we made a change we want to keep going
                                stage += 1
                                run = 0
                                temp = temp*.9
                                #print temp
                                
def flipCoin( p ):
  r = random.random()
  return r < p 

"""
get the number of pixels that are non-background in the QR code
Uses pixel 1,1 as the basis for the background color (Assumption:a buffer
of background exists around the image)

uses python's PIL library: http://www.pythonware.com/products/pil/

x1,y1 is the upper left corner and x2,y2 is the lower right corner of the
QR code. img is the file name
"""
def getOverlap(x1,y1,x2,y2,img):
        image = Image.open(img)
        pixels = image.load()
        cornerPix = pixels[0,0]
        counter = 0
        for i in range(x1,x2+1):
                for j in range(y1,y2+1):
                        if not cornerPix == pixels[i,j]:
                                counter += 1
        if counter == (x2-x1+1)*(y2-y1+1):
                background = pixels[x1,y1]
                for w in range(x1-10,x2+11):
                        for v in range(y1-10,y2+10):
                                if not background == pixels[w,v]:
                                        return counter
                return 0
        else:
                return counter


"""
Returns the list of labels overlapped by the given label
"""
def labelOverlapList(theLabel):
        newOverlap = []
        xOverlap = 0
        yOverlap = 0
        for label in range(len(labelInfo)):
                if theLabel != labelInfo[label]:
                        currentLabelXRange = set(range(theLabel[X1_LABEL], theLabel[X1_LABEL]+theLabel[QR_SIZE_LABEL]))
                        labelXRange = set(range(labelInfo[label][X1_LABEL], labelInfo[label][X2_LABEL]))
                        xIntersection = len(currentLabelXRange.intersection(labelXRange))
                        currentLabelYRange = set(range(theLabel[Y1_LABEL], theLabel[Y1_LABEL]+theLabel[QR_SIZE_LABEL]))
                        labelYRange = set(range(labelInfo[label][Y1_LABEL], labelInfo[label][Y2_LABEL]))
                        yIntersection = len(currentLabelYRange.intersection(labelYRange))
                        overlap = xIntersection*yIntersection
                        if not overlap == 0:
                                newOverlap.append(label)
                        
        return newOverlap


"""
Manhattan Distance of the change of the upper left corner of the QR code
"""
def distFromOriginalPlacement(x1,y1,newX1,newY1):
        return abs(newX1-x1)+abs(newY1-y1)

"""
Returns the number of other labels the given label overlaps
"""
def getNumOverlapped(label):
        return len(label[LABEL_OVERLAP_LIST])


"""
# of pixels of horizontal change - positive for right and negative for left
"""
def distX(x1,newX1):
        return newX1-x1

def weightOverlap(x1,y1,x2,y2,img):
        image = Image.open(img)
        pixels = image.load()
        cornerPix = pixels[0,0]
        middX = (x1+x2)/2.0
        middY = (y1+y2)/2.0
        weightedCount = 0
        yVal = 0
        xVal = 0
        for i in range(x1,x2+1):
                for j in range(y1,y2+1):
                        if not cornerPix == pixels[i,j]:
                                if j>middY:
                                        yVal = y2-j+1
                                else:
                                        yVal = j-y1+1
                                if i>middX:
                                        xVal = x2-i+1
                                else:
                                        xVal = i-x1+1
                                weightedCount += min(xVal,yVal)
        return weightedCount        

"""
For evaluation purposes - will place a black box at the location where the QR code will go and save the file in output folder
"""
def outputImage(img,evalFunc, original):
        image = Image.open(img)
        newIm = image.copy()
        pixels = newIm.load()
        cornerPix = pixels[0,0]
	for label in labelInfo:
                for i in range(label[X1_LABEL],label[X2_LABEL]+1):
                        for j in range(label[Y1_LABEL],label[Y2_LABEL]+1):
                                if original:
                                        pixels[i,j] = (255,0,0) # hexadecimal for red
                                elif sys.argv[3] == "gr":
                                        pixels[i,j] = (0,255,0) # hexadecimal for green
                                else:
                                        pixels[i,j] = (0,0,255) # hexadecimal for blue

        fileName=""
        if evalFunc == "0":
                fileName = "../outputKyle/QR"
        elif evalFunc == "1":
                fileName = "../outputLauren/QR"
        elif evalFunc == "2":
                fileName = "../outputCatie/QR"
        
	if original:
                fileName += img
        else:
                substring =  "." + sys.argv[3] + ".R"
                if evalFunc =="1":
                        substring = ("." + sys.argv[3] + ".L"+ str(WEIGHT_OVERLAPPED_LABEL)
                                     + ".I"+ str(WEIGHT_OVERLAPPED_IMAGE)
                                     + ".X"+ str(WEIGHT_X_DISTANCE_FROM_ORIGINAL)
                                     + ".Y"+ str(WEIGHT_Y_DISTANCE_FROM_ORIGINAL)
                                     + ".M"+ str(MOVEMENT_THRESHOLD)
                                     + ".R")
                img2 = string.replace(img, ".R", substring)
                fileName += img2                     
       
	print fileName 
	newIm.save(fileName)
        
if __name__ == "__main__":
        main()
